<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 分割回文串 -->
    <script>
      var partition = function (s) {
        const n = s.length
        const f = new Array(n).fill([]).map(() => new Array(n).fill(true))

        //动态规划预处理 两次循环遍历 存储字符串所有子串是否为回文字符串 true/false
        for (let i = n - 1; i >= 0; i--) {
          for (let j = i + 1; j < n; j++) {
            f[i][j] = s[i] === s[j] && f[i + 1][j - 1]
          }
        }
        const ans = [],
          res = []
        // 回溯 从0开始进行深度优先遍历

        const dfs = i => {
          // 递归终止条件为 i指针已到字符串最后一个字符 (终止本次递归，因为是循环 所有有多条线路递归)
          if (i === n) return res.push(ans.slice())
          // 循环的目的是 可以取到字符串s的起始位置为i的所有子字符
          for (let j = i; j < n; j++) {
            // 如果是子串会进入下一层
            if (f[i][j]) {
              ans.push(s.slice(i, j + 1))
              dfs(j + 1)
              // 本次递归完需要回到本次循环的上一层状态(回溯)
              ans.pop()
            }
          }
        }
        dfs(0)
        return res
      }
      console.log(partition('aab'))
    </script>
  </body>
</html>
